The ability to make decisions by conditional branching is an essential requirement for any computer system which performs useful work. The decision to branch or not to branch may be based on one or more events. These events, often referred to as conditions, include: positive, negative or zero numbers, overflow, underflow, or carry from the last arithmetic operation, even or odd parity, and many others. Conditional branches are performed in digital computers by conditional branch instructions. Conditional branch instructions may be used to construct such high level programming constructs as loops and if-then-else statements. Because the loops and if-then-else programming constructs are so common, it is essential that the conditional branch instructions which implement them excecute as efficiently as possible.
A computer instruction is executed by performing one or more steps. Typically, these steps are first to fetch the instruction pointed to by a program counter, second to decode and perform the operation indicated by the instruction and finally to save the results. A simple branch instruction changes the contents of the program counter in order to cause execution to "jump" to somewhere else in the program. In order to speed up the execution of computer instructions, a technique of executing more than one instruction at the same time, called pipelining, was developed. Pipelining permits, for example, the central processing unit, CPU, to fetch one instruction while executing another instruction and while saving the results of a third instruction at the same time. In pipelined computer architectures, branching is an expensive operation because branch instructions may cause other instructions in the pipeline to be held up pending the outcome of the branch instruction. When a conditional branch instruction is executed with the condition true, it causes the CPU to continue execution at a new address referred to as a target address. Since instruction fetching is going on simultaneously with instruction decoding and execution in a pipelined computer, the computer has already fetched the instruction following the branch instruction in the program. This is a different instruction than the instruction at the target address. Therefore, the CPU must hold up the instruction pipeline following the branch instruction until the outcome of the branch instruction is known and the proper instruction fetched. In order to maximize throughput of the computer, computer designers have attempted to design computers which maximize throughput by minimizing the need to hold up the instruction pipeline.
In the prior art, several schemes have been used to avoid holding up the instruction pipeline for conditional branches. First, some high performance processors have used various branch prediction schemes to guess whether the conditional branch will be taken or not. This approach requires extensive hardware and is unacceptable in all but the highest performance computers because of the expensive hardware required. Second, other architectures have fetched both the instruction in the program following the branch and the instruction at the branch target address. This approach is unacceptable because it also requires expensive hardware and additional memory accesses to always fetch both instructions. Third, some architectures have a bit in the instruction to tell the computer whether it is more probable for the instruction following the branch or the instruction at the branch target address to be executed. The computer then fetches the more probable instruction and holds up the pipeline only if the guess is wrong. This approach requires expensive hardward and if the guess is wrong causes additional time to be spent backing up the pipeline and fetching appropriate instruction. Fourth, other architectures allow two bits which instruct the CPU to always or never execute the instruction following the branch instruction based on whether the branch is taken or not taken. This architecture uses too many bits from the instruction thereby reducing the maximum range of the branch instruction. Finally, still other architectures always execute the instruction in the program following the branch instruction before taking or not taking the branch.
The technique of executing the instruction in the program following the branch instruction is known as delayed branching. Delayed branching is desirable since the instruction in the pipeline is always executed and the pipeline is not held up. This occurs because delayed branching gives the computer time to execute the branch instruction and compute the address of the next instruction while executing the instruction in the pipeline. Although this technique avoids holding up the instruction pipeline, it may require placing a no operation instruction following the branch instruction, which would not improve performance since the additional memory access negates any improvement.
One software technique which takes advantage of delayed branching is merger. The concept of merger described here is where the loop branch instruction is at the end of the loop. Merger takes advantage of delayed branching by duplicating the first instruction of the loop following the loop's branch instruction and making the branch target address the second instruction of the loop. One potential problem with merger is that on exit from the loop, the program does not necessarily want to execute the merged instruction following the branch instruction again. This is a problem for architectures which always use delayed branching.
When many prior art computer systems determine that a branch is about to be executed, the computer systems hold up, or interlock, the instruction pipeline. Interlocking the pipeline involves stopping the computer from fetching the next instruction and preventing the pipeline from advancing the execution of any of the instructions in the pipeline. Interlocking reduces the performance increase gained by pipelining and therefore is to be avoided.
What is needed is a method of conditional branching which minimizes the amount of hardware and performance reductions. The method should take as few bits of the instruction as possible since each bit taken effectively halves the maximum range of the branch instruction.